package com.example.demo.leetcode;

import java.util.*;

/**
 * 零钱兑换
 * 给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
 * <p>
 * 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
 * <p>
 * 假设每一种面额的硬币有无限个。
 * 输入：amount = 5, coins = [1, 2, 5]
 * 输出：4
 * 解释：有四种方式可以凑成总金额：
 * 5=5
 * 5=2+2+1
 * 5=2+1+1+1
 * 5=1+1+1+1+1
 * 1.先使用dfs 深度优先遍历的方式 递归求解 ，求组合 可以重复
 */
public class Leetcode518 {

    public static void main(String[] args) {

//        System.out.println(new Leetcode518().change(5, new int[]{1, 2, 5}));
        System.out.println(new Leetcode518().change(3, new int[]{2}));
        System.out.println(new Leetcode518().change(10, new int[]{10}));
//        int change = new Leetcode518().change(500, new int[]{3, 5, 7, 8, 9, 10, 11});
//        System.out.println(change);
    }


    public int change(int amount, int[] coins) {
//        List<List<Integer>> res = new ArrayList<>();
//        dfs(0, coins, amount, new LinkedList<>(), res);
//        System.out.println(res.size());
//        System.out.println(res);
//        return res.size();
        return rec(0, coins, amount);
    }

    /**
     * 求出所有可能的组合，筛选出符合条件的组合数
     * 效率太低了
     * 500, new int[]{3, 5, 7, 8, 9, 10, 11没法通过
     */
    private void dfs(int start, int[] coins, int target, LinkedList<Integer> stack, List<List<Integer>> res) {
        Arrays.sort(coins);
        // 1.退出条件
        if (target < 0) {
            return;
        }

        if (target == 0) {
            res.add(new ArrayList<>(stack));
            return;
        }

        for (int i = start; i < coins.length; i++) {
            if (target < coins[i]) {
                continue;
            }
            stack.push(coins[i]);
            dfs(i, coins, target - coins[i], stack, res);
            stack.pop();
        }


        // 2.递归调用

        // 3.回溯

    }

    /**
     * @param index     当前硬币索引
     * @param coins     硬币面值数组
     * @param remainder 剩余金额
     * @return 解的个数
     */
    private int rec(int index, int[] coins, int remainder) {
        // 情况1 剩余金额<0 无解
        //     2 剩余金额>0 继续递归
        //     3 剩余金额==0 算一解

        if (remainder < 0) {
            return 0;
        } else if (remainder > 0) {
            int count = 0;
            for (int i = index; i < coins.length; i++) {
                count += rec(i, coins, remainder - coins[i]);
            }
            return count;
        } else {
            return 1;
        }
    }

}
